import java.util.*;


public class TestDemo3 {
    //判断回文字符串
    public boolean judge(String str) {
        if (str.length() == 0) {
            return true;
        }
        int left = 0;
        int right = str.length() - 1;
        while (left < right) {
            //这里的isLetterOrDigit目的是为了跳过除了字母的元素
            while (left < right && !Character.isLetterOrDigit(str.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(str.charAt(right))) {
                right--;
            }
            //把一些大写的字母转换为小写进行比较
            if (Character.toLowerCase(str.charAt(left)) != Character.toLowerCase(str.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    //截断句子
    public String truncateSentence(String s, int k) {
        int length = s.length();
        int count = 0;
        int end = 0;
        for (int i = 1; i <= length; i++) {
            if (i == length || s.charAt(i) == ' ') {
                count++;
            }
            if (count == k) {
                end = i;
                break;
            }
        }
        //substring是左蔽右开，所以end要取字符长度大小
        return s.substring(0, end);
    }

    //删除重复项
    public int removeDuplicates(int[] nums) {
        int left = 0;
        int right = 1;
        for (right = 1; right < nums.length; right++) {
            if (nums[left] != nums[right]) {
                nums[++left] = nums[right];
            }
        }
        return ++left;//需要++的目的是加上首个元素的个数
    }


    //移除元素
    public static int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;//注意不能是length-1，会少计算一次
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }


    //阿拉伯数字转换
    Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    public int romanToInt(String s) {
        int num = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            int valu = map.get(s.charAt(i));
            if (i < n - 1 && valu < map.get(s.charAt(i + 1))) {
                num -= valu;
            } else {
                num += valu;
            }
        }
        return num;
    }

    //（丑数） 就是只包含质因数 2、3 和/或 5 的正整数。
    public boolean isUgly(int n) {
        if (n < 0) {
            return false;
        }
        int[] factors = {2, 3, 5};
        for (int x : factors) {
            while (n % x == 0) {
                n = n / x;
            }
        }
        return n == 1;
    }

    // 搜索插入位置（oj链接：https://leetcode-cn.com/problems/search-insert-position/）
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

//判定是否互为字符重排(oj链接：https://leetcode-cn.com/problems/check-permutation-lcci/）
    public boolean CheckPermutation(String s1, String s2){
        int len1= s1.length();
        int len2=s2.length();
        Map<Character,Integer>map=new HashMap<>();
        if(len1!=len2){
            return false;
        }
        for(int i=0;i<len1;i++){
            map.put(s1.charAt(i),map.getOrDefault(s1.charAt(i),0)+1);
        }for(int i=0;i<len2;i++){
            map.put(s2.charAt(i),map.getOrDefault(s2.charAt(i),0)-1);
        }
        for(int valu: map.values()){
            if(valu!=0){
                return false;
            }
        }
        return true;
    }


    //最后一块石头的重量(oj链接：https://leetcode-cn.com/problems/last-stone-weight/）
    public int lastStoneWeight(int[] stones){
     Stack<Integer>deque=new Stack<>();
        Stack<Integer>tempDeque=new Stack<>();
        Arrays.sort(stones);
        for(int stone:stones){
            deque.add(stone);
        }
        while(deque.size()>1){
            int newStone=deque.pop()-deque.pop();
            while(deque.size()>0&&deque.peek()>newStone){
                tempDeque.push(deque.pop());
            }deque.push(newStone);
            while(tempDeque.size()>0){
                deque.push(tempDeque.pop());
            }
        }
        return deque.pop();
    }


    //拼写单词（oj链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/）
    public int countCharacters(String[] words, String chars){
        Map<Character,Integer>charMap=new HashMap<>();
        int charsLength=chars.length();
        for(int i=0;i<charsLength;i++){
            char n=chars.charAt(i);
            charMap.put(n,charMap.getOrDefault(n,0)+1);
        }int ans=0;
        for(String x:words){
            Map<Character,Integer>wordsMap=new HashMap<>();
            int wordsLength=x.length();
            for(int i=0;i<wordsLength;i++){
                char m=x.charAt(i);
                wordsMap.put(m,wordsMap.getOrDefault(m,0)+1);//目的是计入放入元素的个数
            }
            boolean tem=true;
            for(int i=0;i<wordsLength;i++){
                char c=x.charAt(i);
                if(charMap.getOrDefault(c,0)<wordsMap.getOrDefault(c,0)){
                    tem=false;
                    break;
                }
            }
            if(tem){
                ans+=x.length();
            }
        }
        return ans;
    }


    //一年中的第几天（oj链接：https://leetcode-cn.com/problems/day-of-the-year/）
    public int dayOfYear(String date){
        int year=Integer.parseInt(date.substring(0,4));//截取字符串中的字符
        int mouth=Integer.parseInt(date.substring(5,7));
        int day=Integer.parseInt(date.substring(8,10));
        int []mouths={31,28,31,30,31,30,31,31,30,31,30,31};
        if(year%400==0||year%4==0&&year%100!=0){
            ++mouths[1];
        }int ans=0;
        for(int i=0;i<mouth-1;i++){
            ans+=mouths[i];
        }
        return ans+day;
    }


    //移除未排序链表中的重复节点。保留最开始出现的节点。（oj链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci/）
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head==null){
            return head;
        }
        Set<Integer>ocurred=new HashSet<Integer>();
        ocurred.add(head.val);
        ListNode tem=head;
        while(tem.next!=null){
            ListNode cur=tem.next;
            if(ocurred.add(cur.val)){//是否可以添加
                tem=tem.next;
            }else{
                tem.next=tem.next.next;//跳过重复的结点
            }
        }tem.next=null;//以防最后一个结点是重复的
        return head;
    }

//两数相加：https://leetcode-cn.com/problems/add-two-numbers/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode head=null;
        ListNode tail=null;
        int carry=0;
        while(l1!=null||l2!=null){
            int n1=l1!=null?l1.val:0;
            int n2=l2!=null?l2.val:0;
            int sum=n1+n2+carry;
            if(head==null){//第一次相加
                head=tail= new ListNode(sum%10);
            }
            else{//之后相加
                tail.next=new ListNode(sum%10);
                tail=tail.next;
            }
            carry=sum/10;//是否需要进位
            if(l1!=null){//计算后面一位
                l1=l1.next;
            }
            if(l2!=null){
                l2=l2.next;
            }
        }
        if(carry>0){//加完之后余数有多要进位
            tail.next=new ListNode(carry);
        }
        return head;
    }
    public ListNode reverseList(ListNode head){
        if(head==null){
            return null;
        }
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        return prev;
    }


}

//oj链接：https://leetcode-cn.com/problems/first-bad-version/
    /*public class Solution extends VersionControl {
        public int firstBadVersion(int n) {
            int left=1;
            int right=n;
            while(left<right){
                int mid=left+(right-left)/2;
                if(isBadVersion(mid)){
                    right=mid;
                }
                else{
                    left=mid+1;
                }
            }
            return left;
        }
    }*/

//猜数字大小
/*class GuessGame {
    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int left = 1, right = n;
            while (left < right) { // 循环直至区间左右端点相同
                int mid = left + (right - left) / 2; // 防止计算时溢出
                if (guess(mid) <= 0) {
                    right = mid; // 答案在区间 [left, mid] 中
                } else {
                    left = mid + 1; // 答案在区间 [mid+1, right] 中
                }
            }
            // 此时有 left == right，区间缩为一个点，即为答案
            return left;
        }
    }

}*/

